package h0808;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

/**
  * @description 二叉树的广度优先遍历
  * @author 不知名帅哥
  * @date 2024/8/8 15:41
  * @version 1.0
*/
public class BinaryTreeBfs2 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String post = sc.next();
        String mid=sc.next();
        System.out.println(getRes(post,mid));
    }

    private static String getRes(String post, String mid) {
        //广度优先搜索的执行队列,先加入左子树,再加入右子树
        LinkedList<String[]> queue=new LinkedList<>();
        //层序遍历出来的元素存放在ans中
        ArrayList<Character> ans=new ArrayList<>();

        devideLR(post,mid,queue,ans);
        while (queue.size()>0){
            String[] tmp=queue.removeFirst();
            devideLR(tmp[0],tmp[1],queue,ans);
        }
        StringBuilder sb=new StringBuilder();
        for (Character c : ans) {
            sb.append(c);
        }
        return sb.toString();
    }

    private static void devideLR(String post, String mid, LinkedList<String[]> queue, ArrayList<Character> ans) {

        //后序遍历的最后一个元素就是根
        char rootVal = post.charAt(post.length() - 1);
        ans.add(rootVal);

        //在中序遍历中找到根的位置,那么该位置左边的就是左子树,右边就是右子树
        int rootIdx = mid.indexOf(rootVal);

        int leftLen=rootIdx;

        if (leftLen>0){
            String leftPost = post.substring(0, leftLen);
            String leftMid = mid.substring(0, leftLen);
            queue.addLast(new String[]{leftPost,leftMid});
        }

        if (post.length()-1-leftLen>0){
            String rightPost = post.substring(leftLen, post.length() - 1);
            String rightMid = mid.substring(leftLen + 1);
            queue.addLast(new String[]{rightPost,rightMid});
        }
    }
}
